package sf.sort;

/**
 * 归并排序
 */
public class MergeSort implements Sort{


    @Override
    public void sort(int[] unsorted) {
        // 第一趟归并是两两归并
        // unsorted[0] change with unsorted[1]
        mergeSort(unsorted, 0, unsorted.length);
    }

    private void mergeSort(int[] part, int l, int m) {
        if (m - l <= 1) {
            return;
        }
        int mid = (l + m) / 2;
        mergeSort(part, l, mid);// sort left
        mergeSort(part, mid, m);// sort right
        // merge
        int k = l;
        int i = l;
        int h = mid;

        int[] newArr = new int[m - l];
        for (; i < m && k < mid && h < m; i++) {
            int left = part[k];
            int right = part[h];
            if (left <= right) {
                newArr[i-l] = left;
                k ++;
            } else {
                newArr[i-l] = right;
                h ++;
            }
        }
        while (i < m && k < mid) {
            newArr[i-l] = part[k];
            i ++;
            k ++;
        }
        while (i < m && h < m) {
            newArr[i-l] = part[h];
            i ++;
            h ++;
        }
        if (m - l >= 0) System.arraycopy(newArr, 0, part, l, m - l);
    }
}
